package DynamicProgrammingPackage;

public class coinChange_ {

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11));
    }

    // 1. dp[j]表示总金额为i的最小硬币数量为dp[j]
    // 2. 递推公式: dp[j] = Math.min(dp[j - coins[i]] + 1,dp[j]) 解释j为总金额设为10,coins[i]为硬币面值 设为5, 总金额10 - 5就组合不为总金额10, 需要在10 - 5基础上再加上5才是一种组合可能
    // 3. 初始化: dp[0] = 0,dp[j] = Int.maxValue
    // 4. 遍历顺序: 完全背包问题 先遍历物品 后遍历背包且背包倒序遍历
    // 求组合总数, 求排列数先正向遍历背包后倒序遍历物品 求组合数 先遍历物品后正向遍历背包
    //
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int j = 1; j <= amount; j++) {
            for (int i = 0 ; i < coins.length; i++) {
                if (coins[i] <= j) {
                    dp[j] = Math.min(dp[j], dp[i - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}
